<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <title>Page Title</title>
    <meta name="viewport" content="width=device-width, initial-scale=1">
</head>

<body>

</body>
<Script>
    function BinaryTree() {
        let node = function (key) {
            this.key = key;
            this.left = null;
            this.right = null;
        };
        this.root = null;
        let insertNode = function (node, newNode) {//插入二叉树
            if (node.key > newNode.key) {
                if (node.left === null) {
                    node.left = newNode;
                } else {
                    insertNode(node.left, newNode);
                }
            } else {
                if (node.right === null) {
                    node.right = newNode;
                } else {
                    insertNode(node.right, newNode);
                }
            }
        };
        this.insert = function (key) {
            if (this.root === null) {
                this.root = new node(key)
            } else {
                insertNode(this.root, new node(key))
            }
        }
        let travelNodeFor = function (node, callBack) {
            if (node !== null) {
                travelNodeFor(node.left, callBack)
                callBack(node.key)
                travelNodeFor(node.right, callBack)
            }
        }
        this.travelNode = function (callBack) {//中序遍历算法
            travelNodeFor(this.root, callBack)
        }
        let beforeNodeFor = function (node, callBack) {
            if (node !== null) {
                callBack(node.key)
                beforeNodeFor(node.left, callBack)
                beforeNodeFor(node.right, callBack)
            }
        }
        this.beforeNode = function (callBack) {//前序遍历算法
            beforeNodeFor(this.root, callBack)
        }
        let afterNodeFor = function (node, callBack) {
            if (node !== null) {
                afterNodeFor(node.left, callBack)
                afterNodeFor(node.right, callBack)
                callBack(node.key)
            }
        }
        this.afterNode = function (callBack) {//后序遍历算法
            afterNodeFor(this.root, callBack)
        }
        this.minNode = function (node) {//最小值
            if (node) {
                while (node && node.left !== null) {
                    node = node.left
                }
                return node.key
            }
            return null
        }
        this.maxNode = function (node) {//最大值
            if (node) {
                while (node && node.right !== null) {
                    node = node.right
                }
                return node.key
            }
            return null
        }
        this.searchNode = function (node, key) {//查找
            if (node == null) {
                return false;
            } else {
                if (node.key > key) {
                    return this.searchNode(node.left, key)
                } else if (node.key < key) {
                    return this.searchNode(node.right, key)
                } else if (node.key == key) {
                    return true;
                }
            }
        }
        this.findMinNode = function (node) {//找到最小节点
            if (node) {
                while (node && node.left !== null) {
                    node = node.left
                }
                return node
            }
            return null
        }
        this.removeNode = function (node, key) {
            if (node == null) {
                return null;
            }
            if (node.key > key) {
                node.left = this.removeNode(node.left, key)
                return node;
            } else if (node.key < key) {
                node.right = this.removeNode(node.right, key)
                return node;
            } else {
                if (node.left == null && node.right == null) {
                    node = null;
                    return node;
                }
                if (node.left == null) {
                    node = node.right;
                    return node;
                }
                if (node.right == null) {
                    node = node.left;
                    return node;
                }
                var aux = this.findMinNode(node.right)
                node.key = aux.key;
                node.right = this.removeNode(node.right, key)
                return node;
            }
        }
        this.remove = function (key) {
            this.root = this.removeNode(this.root, key)
        }
    }

    let nodes = [8, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15];
    let newBanaryTree = new BinaryTree()
    for (let i of nodes) {
        newBanaryTree.insert(i)
    }
    var callBack = function (key) {
        console.log(key + ">>")
    }
    //newBanaryTree.afterNode(callBack)
    //console.log("min:" + newBanaryTree.maxNode(newBanaryTree.root))
    // console.log(newBanaryTree.searchNode(newBanaryTree.root, 22)) 
    newBanaryTree.remove(2)
    console.log(newBanaryTree.root)
</Script>

</html>